package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/11/9
 * Description:
 * -
 * 剑指 Offer 13. 机器人的运动范围
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * <p>
 * 示例 1：
 * <p>
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 * <p>
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 **/
public class QueOffer13 {
    public static void main(String[] args) {

        System.out.println(new Solution().movingCount(38, 15, 9));
    }
    /**
     * 没 10行10列 为一个单元矩阵
     * 左连续: 左向一个矩阵右顶点值 <= k, 意味着10列占满
     * 下连续: 上向一个矩阵下顶点值 <= k, 意味着10行占满
     * 扫描：每增加一行，行起始值+1
     **/
    static class Solution {
        public int movingCount(int m, int n, int k) {
            int c = 0;

            // 每10行 一块 边界条件：前一个块的下顶点的值 <= k 才能连续
            for (int i = 0; i < m && get(i - 1) <= k; i += 10) {
                inner:
                // 每10列 一块 边界条件：前一个块的右顶点的值 <= k 才能连续
                for (int j = 0; j < n && get(i) + get(j - 1) <= k; j += 10) {
                    // 计算块区域起始值 和 横向最大值
                    int s = get(i) + get(j);
                    int max = n - j > 10 ? 10 : n - j;
                    if (s > k) break;

                    // 行扫表，每加行 s+1
                    for (int x = i; x < m && x < i + 10; x++, s++) {
                        int p = cul(s, k, max); // 横向跳段
                        if (p == 0) break inner;
                        c += p;
                    }
                }
            }
            return c;
        }

        public int get(int n) {
            int res = 0;
            while (n != 0) {
                res += n % 10;
                n /= 10;
            }
            return res;
        }

        public int cul(int s, int k, int max) {
            return k - s + 1 > max ? max : k - s + 1;
        }
    }
}
